package com.heima.algorithm.sort;

import java.util.ArrayList;
import java.util.Collections;

/**
 * <h3>桶排序</h3>
 * <ol>
 *     <li>思想就是将数组中不同范围内的元素放到不同的桶中</li>
 *     <li>再用插入排序对各个桶进行排序，最后用各个桶的元素生成排序好的数组</li>
 *     <li>这中间要思考的是怎么让每个桶装的元素接近，比较均匀；以及每个桶装的元素个数不能太小，导致大数据时占用空间大</li>
 * </ol>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/10/6 10:15
 */
public class BucketSort {
    //（1）非比较的排序算法
    //（2）时间复杂度：O(N + K)，空间复杂度：O(N + K)，其中N是数组大小，K是桶的数量，稳定：是

    private static final int DEFAULT_BUCKET_RANGE = 5;

    /**
     * 桶排序，一个桶默认范围5
     * @param arr 待排序数组
     */
    public static void bucketSort(int[] arr) {
        bucketSort(arr, DEFAULT_BUCKET_RANGE);
    }

    /**
     * 桶排序
     * @param arr 待排序数组
     * @param range 一个桶元素大小的范围
     */
    public static void bucketSort(int[] arr, int range) {
        // 找到数组中的最大值和最小值
        int min = arr[0];
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < min){
                min = arr[i];
            }
            if (arr[i] > max){
                max = arr[i];
            }
        }
        // 创建足够数量的桶
        int initialCapacity = (max - min) / range + 1;
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>(initialCapacity);
        // 初始化桶
        for (int i = 0; i < initialCapacity; i++) {
            bucketList.add(new ArrayList<>());
        }
        // 遍历数组，将元素放入桶中
        for (int i : arr) {
            bucketList.get((i - min) / range).add(i);
        }
        // 遍历桶，对桶中的元素进行排序
        int index = 0;
        for (ArrayList<Integer> bucket : bucketList) {
            Collections.sort(bucket);
            for (Integer integer : bucket) {
                arr[index++] = integer;
            }
        }
    }
}
